|
In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way. Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP() refers to the set of decision problems that have probabilistically checkable proofs that can be verified in polynomial time using at most ''r''(''n'') random bits and by reading at most ''q''(''n'') bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem, a major result in computational complexity theory, states that PCP(''n''),O(1) ) = NP. The complexity class PCP is the class of decision problems that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(log ''n'') and query complexity O(1). == Definition == A probabilistically checkable proof system with completeness ''c''(''n'') and soundness ''s''(''n'') over alphabet Σ for a decision problem ''L'', where 0 ≤ ''s''(''n'') ≤ ''c''(''n'') ≤ 1, is a randomized oracle Turing Machine ''V'' (the ''verifier'') that, on input ''x'' and oracle access to a string π ∈ Σ * (the ''proof''), satisfies the following properties: * Completeness: If ''x'' ∈ ''L'' then for some π, ''V''''π''(''x'') accepts with probability at least ''c''(''n''), * Soundness: If ''x'' ∉ ''L'' then for every π, ''V''''π''(''x'') accepts with probability at most ''s''(''n''). The ''randomness complexity'' ''r''(''n'') of the verifier is the maximum number of random bits that ''V'' uses over all ''x'' of length ''n''. The ''query complexity'' ''q''(''n'') of the verifier is the maximum number of queries that ''V'' makes to π over all ''x'' of length ''n''. The verifier is said to be ''non-adaptive'' if it makes all its queries before it receives any of the answers to previous queries. The complexity class PCP''c''(''n''), ''s''(''n'')() is the class of all decision problems having probabilistically checkable proof systems over binary alphabet of completeness ''c''(''n'') and soundness ''s''(''n''), where the verifier is nonadaptive, runs in polynomial time, and it has randomness complexity ''r''(''n'') and query complexity ''q''(''n''). The shorthand notation PCP() is sometimes used for PCP1, ½(). The complexity class PCP is defined as PCP1, ½(). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Probabilistically checkable proof」の詳細全文を読む スポンサード リンク
|